lcmefandomcom_ru-20200213-history
Поиск подстроки
Общая постановка задачи Пусть дан образец Needle длиной n и строка Haystack. Требуется найти такой индекс i, что: \forall l \in \overline {0, n-1}\ haystack_{i+l} = needle_l Либо, если такого индекса не существует, вернуть число, которое не может быть интерпретировано как индекс, например, отрицательное. Наивный алгоритм Идём вперёд по строке и на каждой итерации проверяем, совпадают ли следующие n символов с Needle. let naive_search haystack needle = let needle_len = String.length needle in let search_end = String.length haystack - needle_len in let rec search i = if i > search_end then -1 else if (String.sub haystack i needle_len) = needle then i else search (succ i) in search 0 Как нетрудно заметить, в худшем случае на каждой итерации нужно |needle| - 1 сравнений, всего производится |haystack|-|needle| итераций, поэтому наибольшее количество сравнений, которое, возможно, придётся произвести - это (|haystack|-|needle|)*(|needle|-1) , что соответствует O(|haystack|*|needle|) . Алгоритм Рабина-Карпа Хэш-функции Вообще говоря, хэш-функцией называется функция 'a \to int , дающая более-менее равномерное распределение результатов. Кстати, такая функция представлена в библеотеке OCaml'а. Но в сейчас нас интересует более узкое понятие: хэш-функция строки. Самый простой способ её реализовать - это просто просуммировать коды всех символов. Описание алгоритма Вычислим хэш-функцию от needle и от первых n символов haystack и сравним их. Если совпали, произведём обыкновенное сравнение. Если нет, сдвинем позицию проверки вправо на единицу, вычтем из значения хэш-функции хэш первого символа и прибавим хэш n+1-го. Повторить... let hash s = let sum = ref 0 in for i = 0 to pred (String.length s) do sum := !sum + (int_of_char s.i); done; !sum let rabin_karp haystack needle = let haystack_len = String.length haystack and needle_len = String.length needle in let search_end = haystack_len - needle_len in if search_end < 0 then -1 else let needle_hash = hash needle in let rec search i h = if (i > search_end) then -1 else if (h = needle_hash) && ((String.sub haystack i needle_len) = needle) then i else if (i = search_end) then -1 else search (succ i) (h - (int_of_char haystack.i) + (int_of_char haystack.+ needle_len)) in search 0 (hash (String.sub haystack 0 needle_len)) Алгоритм Кнута-Морриса-Пратта Общее описание Рассмотрим сравнение строк на позиции i, где образец Needle m - 1 сопоставляется с частью текста Haystack [ i, i + m - 1 ] . Предположим, что первое несовпадение произошло между Haystack[ i + j ] и Needle[ j ] , где 1 < j < m . Тогда Haystack[ i, i + j - 1 ] = Needle[ 0, j - 1 ] = P и a = Haystack[ i + j ] \ne Needle[ j ] = b . При сдвиге вполне можно ожидать, что префикс (начальные символы) образца P сойдется с каким-нибудь суффиксом (подсловом) текста P. Длина наиболее длинного префикса, являющегося одновременно суффиксом есть префикс-функция от строки P. let self_repeat s = let len = String.length s in let rec sr i = if (String.sub s 0 i) = (String.sub s (len - i) i) then i else sr (pred i) in if len = 0 then 0 else sr (pred (String.length s)) Таким образом, если при сравнении несовпадение произошло в позиции i, можно сдвигать текущий указатель начала сравнения вперёд не на единицу, а на префикс-функцию от подстроки Needle i - 1 . Классический вариант let kmp haystack needle = let build_backw s = Array.init (String.length s) (fun i -> self_repeat (String.sub s 0 i)) in let backw = build_backw needle and needle_len = String.length needle and haystack_len = String.length haystack in let rec apply i n = if n = needle_len then (i - needle_len) else if i = haystack_len then (-1) else if haystack.i <> needle.n then if n = 0 then apply (succ i) 0 else apply i backw.(n) else apply (succ i) (succ n) in apply 0 0 Автоматный вариант let build_fsm needle = let needle_len = String.length needle in Array.init 256 (fun ch -> Array.init needle_len (fun len -> let c = char_of_int ch in if needle.len = c then succ len else self_repeat ((String.sub needle 0 len) ^ (String.make 1 c)))) let automation haystack needle = let needle_len = String.length needle and haystack_len = String.length haystack and auto = build_fsm needle in let rec apply i n = if n = needle_len then (i - needle_len) else if i = haystack_len then (-1) else find (succ i) (auto.(int_of_char haystack.i).(n)) in apply 0 0 Разница между этими двумя вариантами заключается лишь в том, что автомат строится дольше, чем массив откатов (причём в 256 раз), зато его применение несколько эффективнее, так как массив откатов учитывает все совпавшие символы, а автомат, кроме них, ещё один - тот, на котором произошло несоответствие. Категория:Программирование